(* Fixed Length Codes *)

\(msg = "she sells sea shells by the sea shore"; 

    chars = Characters[msg]\)

alphabet = Union[chars]

Length[alphabet]

fcodes = Table[IntegerDigits[i, 2, 4], {i, 11}]

Thread[{{a, b, c}, {1, 2, 3}}]

Thread[f[{a, b, c}, {1, 2, 3}]]

Thread[f[{a, b, c}, c, {1, 2, 3}]]

Thread[{a, b, c} -> {1, 2, 3}]

Map[(Rule @@ # )& , Transpose[{{a, b, c}, {1, 2, 3}}]]

Transpose[{{a, b, c}, {1, 2, 3}}]

frules = Thread[alphabet -> fcodes]

InputForm[frules = Thread[alphabet -> fcodes]]

InputForm[arules = Thread[fcodes -> alphabet]]

fixedcode[c_String] := c /. frules

TableForm[{InputForm[#], {fixedcode[#]}}& /@ alphabet]

TableForm[{InputForm[#], {fixedcode[#]}}& /@  chars]

encode [code_,  msg_] := Flatten[code /@ Characters[msg]]

encodedmsg = encode[fixedcode,  msg]

Length[encodedmsg]

xmsg = Partition[encodedmsg, {4}]  /. arules

StringJoin @@ xmsg

(* huffman codes *)

pool = {Count[chars, #],  #}& /@ alphabet

pool = Sort[pool]

Take[pool, 2]

Transpose[%]

MapAt[Plus  @@ # &,  %, {1}]

Union[Drop[pool, 2], {%}]

\(combine[x_] := 
      If[Length[x]\  < \ 2, x, 
		
        Union[Drop[x, 2], {
            MapAt[Plus\ @@\ #\ &, \ Transpose[Take[x, 2]], {1}]}]]\)

pool = combine[pool]

pool = combine[pool]

pool = combine[pool]

pool = combine[pool]

FixedPoint[combine, pool]

tree = %[[1, 2]]

Position[tree, "h"]

%[[1]] - 1

Position[tree, "o"]

%[[1]] - 1

variablecode[c_String] := Position[tree, c][[1]] - 1

TableForm[{InputForm[#],  {variablecode[#]}}& /@ alphabet]

encodedtext = encode[variablecode,  msg]

Length[encodedtext]

{1, 0, 1, 0, 0} + 1

Extract[tree, %]

Extract2[list_, {indices__}] := list[[indices]]

{1, 0, 1, 1, 1} + 1

Extract2[tree, %]

code2char[t_List,  c_List] := Extract[t, c + 1]

code2char[tree, {0, 0, 0, 1}]

\(trans[state_List, \ input_Integer] := 
	
      With[{newstate = Append[state, \ input]}, 
		
        If[StringQ[code2char[tree, \ newstate]], 
			
          decoded\  = \ decoded\ <>\ code2char[tree, \ newstate]; {}, 
			
           (*else*) \ newstate\ ]]\)

decoded = "";

FoldList[trans, {}, {0, 1, 0, 0, 1, 1, 1, 1, 1}]

decoded

InputForm[decoded]

decoded = "";

Fold[trans, {}, encodedtext]

InputForm[decoded]

Clear[trans]\(trans[state_List, \ input_Integer] := 
	
      With[{str = state[\([1]\)], \ 
          newpos = Append[state[\([2]\)], \ input]}, 
		
        If[StringQ[code2char[tree, \ newpos]], 

          			{str\ <>\ code2char[tree, \ newpos], {}}, 

          			{str\ , newpos}\ ]]\)

FoldList[trans, {"", {}},  {0, 1, 0, 0, 1, 1, 1, 1, 1}]  // 
      InputForm

Fold[trans, {"", {}},  {0, 1, 0, 0, 1, 1, 1, 1, 1}]

Fold[trans, {"", {}},  encodedtext]

\(Clear[huffmandecode]; 

    huffmandecode[tr_List, \ input_List] := 
      Module[{tree = tr}, \(Fold[trans, {"", {}}, input]\)[\([1]\)\ ]]\)

huffmandecode[tree,  encodedtext]

tree

Clear[trans]\(trans[tr_List] := 
	
      Function[{state, \ input}, 
	
        With[{str = state[\([1]\)], \ 
            newpos = Append[state[\([2]\)], \ input]}, 
		
          If[StringQ[code2char[tr, \ newpos]], 

            			{str\ <>\ code2char[tr, \ newpos], {}}, 

            			{str\ , newpos}\ ]]]\)

trans[tree]

\(Clear[huffmandecode]; 

    huffmandecode[tr_List, \ input_List] := 
      \(Fold[trans[tr], {"", {}}, input]\)[\([1]\)]\)

othertree = tree

Clear[tree]

tree

huffmandecode[othertree,  encodedtext]